import time


def main():
    print("请输入一共有多少个物品：", end=" ")
    count = int(input())
    value = [0]
    weight = [0]
    value_all = input("请输入每个物品的价值：").split(" ")
    for value_one in value_all:
        value.append(int(value_one))
    weight_all = input("请输入每个物品的重量：").split(" ")
    for weight_one in weight_all:
        weight.append(int(weight_one))
    bag_weight = int(input("请输入背包重量："))

    # 保存程序开始时的时间
    time1 = time.perf_counter()
    max_value = [([0] * (bag_weight + 1)) for _ in range(0, count + 1)]
    for i in range(1, count + 1):
        for j in range(1, bag_weight + 1):
            if j >= weight[i]:
                max_value[i][j] = max(max_value[i - 1][j], max_value[i - 1][j - weight[i]] + value[i])
            else:
                max_value[i][j] = max_value[i - 1][j]
    print(max_value)
    print("当背包重量为%d时，能拿物品的最大价值为：%d" % (bag_weight, max_value[count][bag_weight]))
    item = [0 for _ in range(count + 2)]
    m = count
    while m >= 1:
        i = m
        if max_value[i][bag_weight] == max_value[i - 1][bag_weight]:
            item[i] = 0
        else:
            item[i] = 1
            bag_weight -= weight[i]
        m -= 1
    print("所能拿的物品为(1为拿，0为不拿）：", end=" ")
    for i in range(1, count + 1):
        print(item[i], end=" ")
    time2 = time.perf_counter()
    print("\n程序运行时间：%f" % (time2 - time1))


if __name__ == '__main__':
    main()
